/// [Pentagon numbers](https://projecteuler.net/problem=44)
/// P_j = j*(3*j-1)/2
/// P_k = k*(3*k-1)/2, k>j
/// P_k + P_j = k*(3*k-1) + j*(3*j-1) = l*(3*l-1)
/// P_k - P_j = k*(3*k-1) - j*(3*j-1) = x*(3*x-1)
/// P_k = P_j + P_x
/// P_l = P_j + P_k = P_j * 2 + P_x

fn main() {
    let mut pentagonal_number = PentagonalNumber::new();
    'root: for i in 1.. {
        let a = calculate(i);
        for j in 1..2000 {
            let b = calculate(j);
            if a + b < calculate(j + 1) {
                break;
            }
            if pentagonal_number.contain(a + b) && pentagonal_number.contain(a + b * 2) {
                println!("{:6}: {}", i, a);
                println!("{:6}: {}", j, b);
                break 'root;
            }
        }
    }
}

struct PentagonalNumber {
    num: usize,
    buf: Vec<usize>,
}
impl PentagonalNumber {
    pub fn new() -> PentagonalNumber {
        PentagonalNumber { num: 1, buf: vec![1] }
    }
    /// 使用二分法加速
    pub fn contain(&mut self, num: usize) -> bool {
        while num > self.buf[self.buf.len() - 1] {
            self.num += 1;
            self.buf.push(calculate(self.num));
        }
        let (mut l, mut c, mut r) = (0, self.buf.len() / 2, self.buf.len());
        while self.buf[c] != num {
            if c == l {
                return false;
            }
            if self.buf[c] > num {
                r = c;
            } else {
                l = c;
            }
            c = (l + r) / 2;
        }
        true
    }
}

fn calculate(n: usize) -> usize {
    n * (n * 3 - 1) / 2
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn ok_calculate() {
        assert_eq!(calculate(1), 1);
        assert_eq!(calculate(3), 12);
        assert_eq!(calculate(9), 117);
    }
    #[test]
    fn ok_contain() {
        let mut pentagonal_number = PentagonalNumber::new();
        assert!(!pentagonal_number.contain(3797));
        assert!(pentagonal_number.contain(5482660));
    }
}
